home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / utils / sortsrc.arc / sort.c < prev    next >
C/C++ Source or Header  |  1989-03-06  |  18KB  |  432 lines
  1. /******************************************************************************
  2.  *                                                                            *
  3.  *    sort.c     version 1.0 of 22 Januari 1989    (C) L.J.M. de Wit 1989     *
  4.  *                                                                            *
  5.  * This software may be used and distributed freely if not used commercially  *
  6.  * and the originator (me) is mentioned in the source (just leave this 9 line *
  7.  * header intact).                                                            *
  8.  *                                                                            *
  9.  ******************************************************************************
  10.  *
  11.  * sort.c: basic sort functions
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include <osbind.h>
  16. #include "sortmain.h"
  17. #include "sortfile.h"
  18.  
  19. #define LINELEN  256                            /* Max length of input lines*/
  20. #define MAXNAMLEN 80                            /* Max length of filename   */
  21. #define MAXMERGE 8                              /* Max. no of files to be   */
  22.                                                 /* simultaneously merged    */
  23. static int (*cmp)();                            /* Ptr to compare function  */
  24.  
  25. static void sortsub(),                          /* Recursive quicksort      */
  26.             merge();                            /* Merge sorted files       */
  27. static void tempname();                         /* Creates temporary name   */
  28. static int isort();                             /* Initial sort of file(s)  */
  29.  
  30. static char tmpdir[MAXNAMLEN];                  /* Name of temp files dir   */
  31.  
  32. static char insave[2][LINELEN];                 /* Used by unique           */
  33.  
  34. void settemp(tempdir)                           /* Sets the temp files dir  */
  35. char *tempdir;
  36. {
  37.    strcpy(tmpdir,tempdir);
  38. }
  39.  
  40. static void sortsub(sbase,stop)                 /* Sort the pointers        */
  41. char **sbase, **stop;                           /* between sbase and stop   */
  42. {
  43.     register char **base = sbase,               /* All below base and above */
  44.                     **top = stop,               /* top is kept sorted with  */
  45.                     **mid,                      /* respect to element *mid  */
  46.                     *tmp;                       /* For swapping values      */
  47.     register long compfunc = (long)cmp;         /* Kludge to use extra reg. */
  48.  
  49. #define CMP (*(int (*)())compfunc)              /* Replaces (*cmp)          */
  50.  
  51.     mid = base + ((top - base) >> 1);           /* Choose pivot             */
  52.     --top;
  53.     if (top - base >= 6) {                      /* Make sure pivot mid value*/
  54.         if (CMP(*base,*mid) > 0) {
  55.             if (CMP(*mid,*top) <= 0) {
  56.                 if (CMP(*base,*top) > 0) {
  57.                     tmp = *mid;                 /* Swap *mid and *top       */
  58.                     *mid = *top;
  59.                     *top = tmp;
  60.                 } else {
  61.                     tmp = *mid;                 /* Swap *base and *mid      */
  62.                     *mid = *base;
  63.                     *base = tmp;
  64.                 }
  65.             }
  66.         } else if (CMP(*mid,*top) > 0) {
  67.             tmp = *mid;                         /* Swap *mid and *top       */
  68.             *mid = *top;
  69.             *top = tmp;
  70.         }
  71.     } else {                                    /* <= 6 elts: use bubblesort*/
  72.         for ( ; base < top; --top) {
  73.             for (mid = base; mid < top; mid++) {
  74.                 if (CMP(*mid,mid[1]) > 0) {
  75.                     tmp = *mid; *mid = mid[1]; mid[1] = tmp;
  76.                 }
  77.             }
  78.         }
  79.  
  80.         return;                                 /* and return ...           */
  81.     }
  82.     do {
  83.         for ( ; base < mid && CMP(*base,*mid) <= 0; base++) ;
  84.         for ( ; top > mid && CMP(*mid,*top) <= 0; --top) ;
  85.         if (base < top) {
  86.             tmp = *base; *base = *top; *top = tmp; /* Swap *base and *top   */
  87.             if (mid == top) {
  88.                 mid = base;
  89.                 --top;
  90.             } else if (mid == base) {
  91.                 mid = top;
  92.                 base++;
  93.             }
  94.         }
  95.     } while (base < top);                       /* Until all sorted to *mid */
  96.     if (mid - sbase > 1) {                      /* Sort lower half if >1 elt*/
  97.         sortsub(sbase,mid);
  98.     }
  99.     if (stop - mid > 1) {                       /* Sort upper half if >1 elt*/
  100.         sortsub(mid,stop);
  101.     }
  102. }
  103.  
  104. static void merge(infnames,level,
  105.                   startno,nmerge,outfname)      /* Merge sorted input files */
  106. char **infnames;                                /* Input file names array   */
  107. int level,                                      /* No. of times merged      */
  108.     startno,                                    /* Sequence no. within level*/
  109.     nmerge;                                     /* No. of files to merge    */
  110. char *outfname;                                 /* File to be written to    */
  111. {
  112.     static char *inbuf[MAXMERGE];               /* (0)Ptrs to input buffers */
  113.     static FILE *infp[MAXMERGE], *outfp;        /* Input and output FILE *'s*/
  114.     char namebuf[MAXNAMLEN];                    /* To store temp file names */
  115.     char *nameptr;
  116.     int cur,                                    /* Number of current file   */
  117.         i, j,
  118.         nbusy = 0,                              /* # of input files in use  */
  119.         tmp;
  120.     int order[MAXMERGE];                        /* Ordering of file numbers */
  121.     char *s;
  122.     long avail;
  123.  
  124.     avail = (Malloc(-1) - 20480) & ~1;          /* Get free - 20K           */
  125.     avail /= nmerge + 1;
  126.     avail -= avail % 2048;
  127.  
  128.     if (outfname == (char *)0) {
  129.         outfp = stdout;                         /* stdout is default        */
  130.     } else {
  131.         outfp = fopen(outfname,"w");
  132.         if (outfp == (FILE *)0) {
  133.             error("%s: cannot open for write\n",outfname);
  134.         }
  135.     }
  136.  
  137.     if ((s = (char *)Malloc(avail)) == (char *)-1) { /* Grab it     */
  138.         error("memory allocation failed\n",(char *)0);
  139.     }
  140.     setbuffer(outfp,s,avail);
  141.  
  142.     if (level < 0) {
  143.         if (*infnames != (char *)0) {
  144.             for (i = 0; i < startno; i++) {
  145.                 infnames++;
  146.             }
  147.         }
  148.     }
  149.  
  150.     for (i = 0; i < nmerge; i++) {              /* Open each input file     */
  151.         if (level < 0) {
  152.             nameptr = *infnames++;
  153.         } else {
  154.             tempname(namebuf,level,startno+i);
  155.             nameptr = namebuf;
  156.         }
  157.         if (nameptr == (char *)0 || !strcmp(nameptr,"-")) {
  158.             infp[i] = stdin;                    /* stdin is default         */
  159.         } else {
  160.             infp[i] = fopen(nameptr,"r");
  161.             if (infp[i] == (FILE *)0) {
  162.                 error("%s: cannot open for read\n",nameptr);
  163.             }
  164.         }
  165.         if ((s = (char *)Malloc(avail)) == (char *)-1) { /* Grab it     */
  166.             error("memory allocation failed\n",(char *)0);
  167.         }
  168.         setbuffer(infp[i],s,avail);
  169.  
  170.         if (inbuf[i] == (char *)0) {            /* Possibly allocate buffer */
  171.             if ((inbuf[i] = (char *)malloc(LINELEN)) == (char *)0) {
  172.                 error("memory allocation failed\n",(char *)0);
  173.             }
  174.         }
  175.         if (fgets(inbuf[i],LINELEN,infp[i]) != (char *)0) { /* Read 1st line*/
  176.             order[nbusy++] = i;                 /* Enter its seq no.        */
  177.             for (j = nbusy - 1; j >= 1 &&       /* Put in place in order    */
  178.                        (*cmp)(inbuf[order[j-1]],inbuf[order[j]]) > 0; --j) {
  179.                 tmp = order[j-1]; order[j-1] = order[j]; order[j] = tmp;
  180.             }
  181.         }
  182.     }
  183.  
  184.     if ((options & UNIQUE) && nbusy > 0) {
  185.         insave[0][0] = inbuf[order[0]][0] + 1;  /* Force difference */
  186.     }
  187.  
  188.     while (nbusy > 0) {
  189.         cur = order[0];                         /* No. of lowest ordered    */
  190.         if (options & UNIQUE) {
  191.             if ((*cmp)(inbuf[cur],insave[0])) { /* Differs from previous one*/
  192.                 fputs(inbuf[cur],outfp);        /* Write out lowest ordered */
  193.                 strcpy(insave[0],inbuf[cur]);
  194.             }
  195.         } else {
  196.             fputs(inbuf[cur],outfp);            /* Write out lowest ordered */
  197.